﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FrogEngine
{
	public enum TreeColor
	{
		Red,
		Black
	}

	public interface IRedBlackTreeNode<K, T> : IBinaryTreeNode<K, T>
	{
		TreeColor Color { get; set; }
		IRedBlackTreeNode<K, T> Sibling();
		IRedBlackTreeNode<K, T> Uncle();
		IRedBlackTreeNode<K, T> GrandParent();
	}

	public class RedBlackTreeNode<K, T> : IRedBlackTreeNode<K, T>
	{
		public IRedBlackTreeNode<K, T> GrandParent()
		{
			if (this.Parent != null)
				return (IRedBlackTreeNode<K, T>)this.Parent.Parent;
			else return null;
		}

		public IRedBlackTreeNode<K, T> Uncle()
		{
			var g = this.GrandParent();
			if (g == null)
				return null;
			if (this.Parent == g.Left)
				return (IRedBlackTreeNode<K, T>)g.Right;
			else
				return (IRedBlackTreeNode<K, T>)g.Left;
		}

		public IRedBlackTreeNode<K, T> Sibling()
		{
			if (this == this.Parent.Left)
				return (IRedBlackTreeNode<K, T>)this.Parent.Right;
			else
				return (IRedBlackTreeNode<K, T>)this.Parent.Left;
		}

		private TreeColor color;
		public TreeColor Color
		{
			get { return color; }
			set { color = value; }
		}

		private IBinaryTreeNode<K, T> parent;
		public IBinaryTreeNode<K, T> Parent
		{
			get { return parent; }
			set { parent = value; }
		}

		private IBinaryTreeNode<K, T> left;
		public IBinaryTreeNode<K, T> Left
		{
			get { return left; }
			set { left = value; }
		}

		private IBinaryTreeNode<K, T> right;
		public IBinaryTreeNode<K, T> Right
		{
			get { return right; }
			set { right = value; }
		}

		private K key;
		public K Key
		{
			get { return key; }
			set { key = value; }
		}

		private T val;
		public T Value
		{
			get { return val; }
			set { val = value; }
		}

		public bool IsExternal
		{
			get { return left == null && right == null; }
		}

		private bool visited;
		public bool Visited
		{
			get { return visited; }
			set { visited = value; }
		}
	}

	public class RedBlackTree<K, T> : BinaryTreeCommon<K, T>, IBinarySearchTree<K, T, IRedBlackTreeNode<K, T>>
		where K : IComparable
	{
		protected override IBinaryTreeNode<K, T> CreateNode(IBinaryTreeNode<K, T> parent, K key, T item)
		{
			return new RedBlackTreeNode<K, T> { Parent = parent, Key = key, Value = item, Color = TreeColor.Black };
		}

		public IRedBlackTreeNode<K, T> Find(IRedBlackTreeNode<K, T> start, K key)
		{
			if (start.IsExternal)
				return start;
			int compareVal = key.CompareTo(start.Key); // Comparer<K>.Default.Compare(key, start.Key);
			if (compareVal < 0)
				return Find((IRedBlackTreeNode<K, T>)start.Left, key);
			else if (compareVal > 0)
				return Find((IRedBlackTreeNode<K, T>)start.Right, key);
			else
				return start;
		}

		public override void InsertItem(K key, T item)
		{
			if (Root == null)
			{
				Root = new RedBlackTreeNode<K, T> { Color = TreeColor.Black, Parent = null, Key = key, Value = item };
				Root.Left = new RedBlackTreeNode<K, T> { Parent = Root, Color = TreeColor.Black };
				Root.Right = new RedBlackTreeNode<K, T> { Parent = Root, Color = TreeColor.Black };
				return;
			}

			var insertionNode = Find(Root, key);
			insertionNode.Key = key;
			insertionNode.Value = item;
			insertionNode.Color = TreeColor.Red;
			insertionNode.Left = new RedBlackTreeNode<K, T> { Color = TreeColor.Black, Parent = insertionNode, Left = null, Right = null };
			insertionNode.Right = new RedBlackTreeNode<K, T> { Color = TreeColor.Black, Parent = insertionNode, Left = null, Right = null };

			insertCase1(insertionNode);
		}

		#region [ Insert Cases ]

		private void insertCase1(IRedBlackTreeNode<K, T> node)
		{
			if (node == Root)
			{
				node.Color = TreeColor.Black;
			}
			else
				insertCase2(node);
		}

		private void insertCase2(IRedBlackTreeNode<K, T> node)
		{
			if ((node.Parent as IRedBlackTreeNode<K, T>).Color == TreeColor.Black)
				return;
			else
				insertCase3(node);
		}

		private void insertCase3(IRedBlackTreeNode<K, T> node)
		{
			if (node.Uncle() != null && node.Uncle().Color == TreeColor.Red)
			{
				var v = node.Parent as IRedBlackTreeNode<K, T>;
				v.Color = TreeColor.Black;
				node.Uncle().Color = TreeColor.Black;
				var u = node.GrandParent();
				if (u == Root)
					return;
				u.Color = TreeColor.Red;
				insertCase1(u);
			}
			else
				insertCase4(node);
		}

		private void insertCase4(IRedBlackTreeNode<K, T> node)
		{
			var g = node.GrandParent();
			if (node == node.Parent.Right && node.Parent == g.Left)
			{
				RotateLeft((IRedBlackTreeNode<K, T>)node.Parent);
				node = (IRedBlackTreeNode<K, T>)node.Left;
			}
			else if (node == node.Parent.Left && node.Parent == g.Right)
			{
				RotateRight((IRedBlackTreeNode<K, T>)node.Parent);
				node = (IRedBlackTreeNode<K, T>)node.Right;
			}
			insertCase5(node);
		}

		private void insertCase5(IRedBlackTreeNode<K, T> node)
		{
			var g = node.GrandParent();
			(node.Parent as IRedBlackTreeNode<K, T>).Color = TreeColor.Black;
			g.Color = TreeColor.Red;
			if ((node == node.Parent.Left) && (node.Parent == g.Left))
				RotateRight(g);
			else if ((node == node.Parent.Right) && (node.Parent == g.Right))
				RotateLeft(g);
		}

		#endregion

		private void RotateLeft(IRedBlackTreeNode<K, T> x)
		{
			IRedBlackTreeNode<K, T> y = x.Right as IRedBlackTreeNode<K, T>;
			x.Right = y.Left;
			if (y.Left != null)
				y.Left.Parent = x;
			y.Parent = x.Parent;
			if (x.Parent == null)
				Root = y;
			else
				if (x == x.Parent.Left)
					x.Parent.Left = y;
				else
					x.Parent.Right = y;
			y.Left = x;
			x.Parent = y;
		}

		private void RotateRight(IRedBlackTreeNode<K, T> x)
		{
			IRedBlackTreeNode<K, T> y = x.Left as IRedBlackTreeNode<K, T>;
			x.Left = y.Right;
			if (y.Right != null)
				y.Right.Parent = x;
			y.Parent = x.Parent;
			if (x.Parent == null)
				Root = y;
			else
				if (x == x.Parent.Right)
					x.Parent.Right = y;
				else
					x.Parent.Left = y;
			y.Right = x;
			x.Parent = y;
		}

		public void RemoveItem(K key)
		{
			var node = Find(Root, key);
			if (node.Key.CompareTo(key) == 0)
			{
				Remover(node);
			}
		}

		private void ReplaceNode(IRedBlackTreeNode<K, T> n, IRedBlackTreeNode<K, T> child)
		{
			var p = n.Parent;
			if (n == p.Left)
				p.Left = child;
			else
				p.Right = child;
			child.Parent = p;
		}

		private void delete_one(IRedBlackTreeNode<K, T> node)
		{
			var child = node.Right.IsExternal ? node.Left as IRedBlackTreeNode<K, T> : node.Right as IRedBlackTreeNode<K, T>;
			ReplaceNode(node, child);
			if (node.Color == TreeColor.Black)
				if (child.Color == TreeColor.Red)
					child.Color = TreeColor.Black;
				else
					deleteCase1(child);
			node = null;
		}

		#region [ Delete Cases ]

		private void deleteCase1(IRedBlackTreeNode<K, T> node)
		{
			if (node.Parent != null)
				deleteCase2(node);
		}

		private void deleteCase2(IRedBlackTreeNode<K, T> node)
		{
			var s = node.Sibling();

			if (s.Color == TreeColor.Red)
			{
				(node.Parent as IRedBlackTreeNode<K, T>).Color = TreeColor.Red;
				s.Color = TreeColor.Black;
				if (node == node.Parent.Left)
					RotateLeft(node.Parent as IRedBlackTreeNode<K, T>);
				else
					RotateRight(node.Parent as IRedBlackTreeNode<K, T>);
			}
			deleteCase3(node);
		}

		private void deleteCase3(IRedBlackTreeNode<K, T> node)
		{
			var s = node.Sibling();

			if ((node.Parent as IRedBlackTreeNode<K, T>).Color == TreeColor.Black
				&& s.Color == TreeColor.Black
				&& (s.Left as IRedBlackTreeNode<K, T>).Color == TreeColor.Black
				&& (s.Right as IRedBlackTreeNode<K, T>).Color == TreeColor.Black)
			{
				s.Color = TreeColor.Red;
				deleteCase1(node.Parent as IRedBlackTreeNode<K, T>);
			}
			else
				deleteCase4(node);
		}

		private void deleteCase4(IRedBlackTreeNode<K, T> node)
		{
			var s = node.Sibling();

			if ((node.Parent as IRedBlackTreeNode<K, T>).Color == TreeColor.Red
				&& s.Color == TreeColor.Black
				&& (s.Left as IRedBlackTreeNode<K, T>).Color == TreeColor.Black
				&& (s.Right as IRedBlackTreeNode<K, T>).Color == TreeColor.Black)
			{
				s.Color = TreeColor.Red;
				(node.Parent as IRedBlackTreeNode<K, T>).Color = TreeColor.Black;
			}
			else
				deleteCase5(node);
		}

		private void deleteCase5(IRedBlackTreeNode<K, T> node)
		{
			var s = node.Sibling();

			if (s.Color == TreeColor.Black)
			{
				if (node == node.Parent.Left
					&& (s.Right as IRedBlackTreeNode<K, T>).Color == TreeColor.Black
					&& (s.Left as IRedBlackTreeNode<K, T>).Color == TreeColor.Red)
				{
					s.Color = TreeColor.Red;
					(s.Left as IRedBlackTreeNode<K, T>).Color = TreeColor.Black;
					RotateRight(s);
				}
				else if (node == node.Parent.Right
					&& (s.Left as IRedBlackTreeNode<K, T>).Color == TreeColor.Black
					&& (s.Right as IRedBlackTreeNode<K, T>).Color == TreeColor.Red)
				{
					s.Color = TreeColor.Red;
					(s.Right as IRedBlackTreeNode<K, T>).Color = TreeColor.Black;
					RotateLeft(s);
				}
			}
			deleteCase6(node);
		}

		private void deleteCase6(IRedBlackTreeNode<K, T> node)
		{
			var s = node.Sibling();
			s.Color = (node.Parent as IRedBlackTreeNode<K, T>).Color;
			(node.Parent as IRedBlackTreeNode<K, T>).Color = TreeColor.Black;

			if (node == node.Parent.Left)
			{
				(s.Right as IRedBlackTreeNode<K, T>).Color = TreeColor.Black;
				RotateLeft(node.Parent as IRedBlackTreeNode<K, T>);
			}
			else
			{
				(s.Left as IRedBlackTreeNode<K, T>).Color = TreeColor.Black;
				RotateRight(node.Parent as IRedBlackTreeNode<K, T>);
			}
		}

		#endregion

		private void Remover(IRedBlackTreeNode<K, T> node)
		{
			if (node.Left.IsExternal)
			{
				delete_one(node);
			}
			else if (node.Right.IsExternal)
			{
				delete_one(node);
			}
			else
			{
				var rightSub = node.Right;
				IBinaryTreeNode<K, T> min = rightSub;
				while (!min.Left.IsExternal)
					min = min.Left;
				node.Key = min.Key;
				node.Value = min.Value;
				delete_one(min as IRedBlackTreeNode<K, T>);
			}
		}

		public new IRedBlackTreeNode<K, T> Root
		{
			get { return (IRedBlackTreeNode<K, T>)base.Root; }
			set { base.Root = value; }
		}

		public int Height(IRedBlackTreeNode<K, T> start)
		{
			return base.Height(start);
		}

		public int Depth(IRedBlackTreeNode<K, T> node)
		{
			return base.Depth(node);
		}

		public void PreOrderTraversal<Y>(IRedBlackTreeNode<K, T> start, Action<Y> visitAction)
		{
			base.PreOrderTraversal<Y>(start, visitAction);
		}

		public void PostOrderTraversal<Y>(IRedBlackTreeNode<K, T> start, Action<Y> visitAction)
		{
			base.PostOrderTraversal<Y>(start, visitAction);
		}

		public void InOrderTraversal<Y>(IRedBlackTreeNode<K, T> start, Action<Y> visitedAction)
		{
			base.InOrderTraversal<Y>(start, visitedAction);
		}
	}
}
